/**  
 * Copyright (c) 2010 University of Pennsylvania.
 *     All rights reserved.
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an "AS
 *  IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
 *  express or implied.  See the License for the specific language
 *  governing permissions and limitations under the License.
 *
 */
 
void multicast_insertpath(MULTICAST_NODE **p, ADDRESS *path, uint8_t path_len, uint8_t node_level,
  uint8_t multiplicity)
{                     // add a new path to the multicast tree, recursive function
  int i, k;
  MULTICAST_NODE *p1;

  if (*p == NULL)             // insert as leaf in tree
  {
    *p = (MULTICAST_NODE *) mmalloc(sizeof(MULTICAST_NODE));

    (*p)->path_len = path_len;
    if (path_len > 0)
    {
      (*p)->path = (ADDRESS *) mcalloc(sizeof(ADDRESS), path_len);
      memcpy((*p)->path, path, path_len*sizeof(ADDRESS));
    } else (*p)->path = NULL;
      
    (*p)->send_here = 1;
    (*p)->node_level = node_level;
    (*p)->multiplicity = multiplicity;
    (*p)->child_count = 0;
    (*p)->children = NULL;
  } else {
    k = 0;
    while (k < (*p)->path_len && k < path_len && (*p)->path[k] == path[k])
      k++;

    if (k >= (*p)->path_len && k < path_len)                 // shared path is longer than path to internal node p
    {
      i = 0;
      while (i < (*p)->child_count)
      {
        if ((*p)->children[i]->path[0] == path[k])           // existing leaf is a prefix of currect path
        {
          multicast_insertpath(&(*p)->children[i], &path[k], path_len-k, node_level, multiplicity);
          break;
        }
        i++;
      }

      if (i >= (*p)->child_count)                            // no leaf is a prefix of current path
      {
        (*p)->child_count++;
        (*p)->children = (MULTICAST_NODE **)
          mrealloc((*p)->children, sizeof(MULTICAST_NODE *)*(*p)->child_count);
        (*p)->children[(*p)->child_count-1] = NULL;
        multicast_insertpath(&(*p)->children[(*p)->child_count-1], &path[k], path_len-k, node_level,
          multiplicity);
      }
    } else if (k >= (*p)->path_len && k >= path_len)         // existing leaf conincides with path we insert
    {
      (*p)->send_here = 1;
      (*p)->node_level = node_level;
      (*p)->multiplicity = multiplicity;
    } else {                                                   // shared path shorter than path to internal node p
      p1 = (MULTICAST_NODE *) mmalloc(sizeof(MULTICAST_NODE));

      p1->path_len = (*p)->path_len-k;
      if (p1->path_len > 0)
      {
        p1->path = (ADDRESS *) mcalloc(p1->path_len, sizeof(ADDRESS));
        memcpy(p1->path, &(*p)->path[k], p1->path_len*sizeof(ADDRESS));
      } else p1->path = NULL;

      p1->send_here = (*p)->send_here;
      p1->node_level = (*p)->node_level;
      p1->multiplicity = (*p)->multiplicity;
      p1->child_count = (*p)->child_count;
      p1->children = (*p)->children;

      (*p)->path_len = k;
      (*p)->path = (k > 0) ? ((ADDRESS *) mrealloc((*p)->path, sizeof(ADDRESS)*k)) : NULL;

      if (k < path_len)
      {
        (*p)->send_here = 0;
        (*p)->node_level = 0;
        (*p)->multiplicity = 0;
        (*p)->child_count = 2;
        (*p)->children = (MULTICAST_NODE **) mcalloc(sizeof(MULTICAST_NODE *), (*p)->child_count);
        (*p)->children[0] = p1;

        p1 = (MULTICAST_NODE *) mmalloc(sizeof(MULTICAST_NODE));

        p1->path_len = path_len-k;
        if (p1->path_len > 0)
        {
          p1->path = (ADDRESS *) mcalloc(sizeof(ADDRESS), p1->path_len);
          memcpy(p1->path, &path[k], p1->path_len*sizeof(ADDRESS));
        } else p1->path = NULL;

        p1->send_here = 1;
        p1->node_level = node_level;
        p1->multiplicity = multiplicity;
        p1->child_count = 0;
        p1->children = NULL;
        (*p)->children[1] = p1;
      } else {
        (*p)->send_here = 1;
        (*p)->node_level = node_level;
        (*p)->multiplicity = multiplicity;
        (*p)->child_count = 1;
        (*p)->children = (MULTICAST_NODE **) mcalloc(sizeof(MULTICAST_NODE *), (*p)->child_count);
        (*p)->children[0] = p1;
      }
    }
  }
}

void marshal_multicast(uint8_t **pos, MULTICAST_NODE *n, uint8_t level)
{                                   // marshal the multicast tree into a buffer, recursive
  uint8_t i, t, *ofs;

  if (n == NULL)
    return;

  ofs = *pos;

  t = (n->send_here << 7) | ((n->child_count < 8 && n->path_len < 8) << 6);
  if (n->child_count < 8 && n->path_len < 8)
  {
    t |= ((n->path_len << 3) | n->child_count);
    marshal_byte(pos, t);
  } else {
    t |= n->child_count;

    marshal_byte(pos, t);
    if (level > 0)
      marshal_byte(pos, n->path_len);
  }

  if (level > 0)
    marshal_pathvec(pos, n->path, n->path_len);

  for (i = 0; i < n->child_count; i++)
    marshal_multicast(pos, n->children[i], level+1);

  n->marshal_size = *pos-ofs;
}

void unmarshal_multicast(uint8_t **pos, MULTICAST_NODE **n, uint8_t level)
{                                       // unmarshal buffer and build a multicast tree, recursive
  uint8_t i, t;

  if (*n == NULL)
  {
    *n = (MULTICAST_NODE *) mmalloc(sizeof(MULTICAST_NODE));
    memset(*n, 0, sizeof(MULTICAST_NODE));
  }

  t = unmarshal_byte(pos);
  (*n)->send_here = (t & 0x80) != 0;
  if (t & 0x40)
  {
    (*n)->path_len = (level > 0) ? (t >> 3) & 0x07 : 0;
    (*n)->child_count = t & 0x07;
  } else {
    (*n)->child_count = t & 0x3f;
    (*n)->path_len = (level > 0) ? unmarshal_byte(pos) : 0;
  }

  if (level > 0)
  {
    (*n)->path = (ADDRESS *) mcalloc((*n)->path_len, sizeof(ADDRESS));
    unmarshal_pathvec(pos, (*n)->path, (*n)->path_len);
  } else (*n)->path = NULL;

  if ((*n)->child_count > 0)
  {
    (*n)->children = (MULTICAST_NODE **) mcalloc((*n)->child_count, sizeof(MULTICAST_NODE *));
    for (i = 0; i < (*n)->child_count; i++)
    {
      (*n)->children[i] = NULL;
      unmarshal_multicast(pos, &(*n)->children[i], level+1);
    }
  } else (*n)->children = NULL;
}

void multicast_free(MULTICAST_NODE *n)  // free a multicast tree from the heap
{
  int i;

  if (n == NULL)
    return;

  if (n->path)
    mfree(n->path);

  if (n->children)
  {
    for (i = 0; i < n->child_count; i++)
      multicast_free(n->children[i]);
    mfree(n->children);
  }
  
  mfree(n);
}

void multicast_print(MULTICAST_NODE *n, uint8_t level)   // print a multicast tree, for debugging
{
  int i,len;
  char s[256];

  s[0] = 0;
  for (i = 0; i < level; i++)
  {
    len = strlen(s);
    sprintf(&s[len], "    ");
  }
  
  if (n->path)
    for (i = 0; i < n->path_len; i++)
    {
      len = strlen(s);
      sprintf(&s[len], "%d ", n->path[i]);
    }
    
  if (n->send_here)
  {
    len = strlen(s);
    sprintf(&s[len], "*");  
  }
  
  len = strlen(s);
  sprintf(&s[len], "L: %d, M: %d, S: %d", n->node_level, n->multiplicity, n->marshal_size);
  DBGOUT(s);

  for (i = 0; i < n->child_count; i++)
    multicast_print(n->children[i], level+1);
}


